On the combinatorial complexity of fuzzy pattern matching in music analysis
Identifieur interne : 000386 ( Main/Exploration ); précédent : 000385; suivant : 000387On the combinatorial complexity of fuzzy pattern matching in music analysis
Auteurs : Richard E. Overill [Royaume-Uni]Source :
- Computers and the Humanities [ 0010-4817 ] ; 1993.
English descriptors
- Entity :
- pers : A. Given, Andrew Wells, C.Eng, C.Math, Dr Alastair, J.S.Bach, John Blitheman, John Martin, Richard E. Overill, Thomas TaIlis, William Byrd.
- place : Model.
- Teeft :
- Adjacent symbols, Approximate string, College london, Combinatorial complexity, Computer science, Computerassisted music analysis, Consecutive symbols, Distinguishable symbols, Emax, Exact transpositions, Extra note, Extra notes, Extra symbols, Fewer notes, Fewer symbols, Fibonacci sequence, Fmax, Fuzzy pattern, Imax, Imax inaccuracy, Imax semitones inaccuracy, Inaccuracy, Inaccurate symbols, Initial string, Maximum number, Music analysis, Musical score, Recurrence, Recurrence relations, Symbol string, Time complexity, Total number, Total time, Variant, Variants model.
Abstract
Abstract: In music analysis it is a common requirement to search a musical score for occurrences of a particular musical motif and its variants. This tedious and time-consuming task can be carried out by computer, using one of several models to specify which variants are to be included in the search. The question arises: just how many variants must be explicitly considered? The answer has a profound effect on the computer time needed. In this paper, recurrence relations and closed form analytic expressions are derived for the run time complexity of two models of “fuzzy pattern matching” for use in music analysis; each model assumes the existence of an atomic exact pattern matching operation. The formulae so obtained are evaluated and tabulated as a function of their independent parameters. These results enable a priori estimates to be made of the relative run times of different music searches performed using either model. This is illustrated by applying the results to an actual musical example.
Url:
DOI: 10.1007/BF01830303
Affiliations:
Links toward previous steps (curation, corpus...)
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">On the combinatorial complexity of fuzzy pattern matching in music analysis</title><author><name sortKey="Overill, Richard E" sort="Overill, Richard E" uniqKey="Overill R" first="Richard E." last="Overill">Richard E. Overill</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:460CFF3C36C956DD999D7F3A6F79B7908496BE3C</idno><date when="1993" year="1993">1993</date><idno type="doi">10.1007/BF01830303</idno><idno type="url">https://api.istex.fr/ark:/67375/1BB-4CRNSX13-S/fulltext.pdf</idno><idno type="wicri:Area/Main/Corpus">000029</idno><idno type="wicri:explorRef" wicri:stream="Main" wicri:step="Corpus" wicri:corpus="ISTEX">000029</idno><idno type="wicri:Area/Main/Curation">000029</idno><idno type="wicri:Area/Main/Exploration">000386</idno><idno type="wicri:explorRef" wicri:stream="Main" wicri:step="Exploration">000386</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">On the combinatorial complexity of fuzzy pattern matching in music analysis</title><author><name sortKey="Overill, Richard E" sort="Overill, Richard E" uniqKey="Overill R" first="Richard E." last="Overill">Richard E. Overill</name><affiliation wicri:level="3"><country xml:lang="fr">Royaume-Uni</country><wicri:regionArea>Algorithm Design Group, Department of Computer Science, King's College London, WC2R 2LS, Strand, London</wicri:regionArea><placeName><settlement type="city">Londres</settlement><region type="country">Angleterre</region><region type="région" nuts="1">Grand Londres</region></placeName></affiliation><affiliation></affiliation></author></analytic><monogr></monogr><series><title level="j" type="main">Computers and the Humanities</title><title level="j" type="abbrev">Comput Hum</title><idno type="ISSN">0010-4817</idno><idno type="eISSN">1572-8412</idno><imprint><publisher>Kluwer Academic Publishers</publisher><pubPlace>Dordrecht</pubPlace><date type="published" when="1993">1993</date><biblScope unit="vol" from="27" to="27">27</biblScope><biblScope unit="issue" from="2" to="2">2</biblScope><biblScope unit="page" from="105">105</biblScope><biblScope unit="page" to="110">110</biblScope></imprint><idno type="ISSN">0010-4817</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0010-4817</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="Entity" type="pers" xml:lang="en"><term>A. Given</term><term>Andrew Wells</term><term>C.Eng</term><term>C.Math</term><term>Dr Alastair</term><term>J.S.Bach</term><term>John Blitheman</term><term>John Martin</term><term>Richard E. Overill</term><term>Thomas TaIlis</term><term>William Byrd</term></keywords><keywords scheme="Entity" type="place" xml:lang="en"><term>Model</term></keywords><keywords scheme="Teeft" xml:lang="en"><term>Adjacent symbols</term><term>Approximate string</term><term>College london</term><term>Combinatorial complexity</term><term>Computer science</term><term>Computerassisted music analysis</term><term>Consecutive symbols</term><term>Distinguishable symbols</term><term>Emax</term><term>Exact transpositions</term><term>Extra note</term><term>Extra notes</term><term>Extra symbols</term><term>Fewer notes</term><term>Fewer symbols</term><term>Fibonacci sequence</term><term>Fmax</term><term>Fuzzy pattern</term><term>Imax</term><term>Imax inaccuracy</term><term>Imax semitones inaccuracy</term><term>Inaccuracy</term><term>Inaccurate symbols</term><term>Initial string</term><term>Maximum number</term><term>Music analysis</term><term>Musical score</term><term>Recurrence</term><term>Recurrence relations</term><term>Symbol string</term><term>Time complexity</term><term>Total number</term><term>Total time</term><term>Variant</term><term>Variants model</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: In music analysis it is a common requirement to search a musical score for occurrences of a particular musical motif and its variants. This tedious and time-consuming task can be carried out by computer, using one of several models to specify which variants are to be included in the search. The question arises: just how many variants must be explicitly considered? The answer has a profound effect on the computer time needed. In this paper, recurrence relations and closed form analytic expressions are derived for the run time complexity of two models of “fuzzy pattern matching” for use in music analysis; each model assumes the existence of an atomic exact pattern matching operation. The formulae so obtained are evaluated and tabulated as a function of their independent parameters. These results enable a priori estimates to be made of the relative run times of different music searches performed using either model. This is illustrated by applying the results to an actual musical example.</div></front></TEI><affiliations><list><country><li>Royaume-Uni</li></country><region><li>Angleterre</li><li>Grand Londres</li></region><settlement><li>Londres</li></settlement></list><tree><country name="Royaume-Uni"><region name="Angleterre"><name sortKey="Overill, Richard E" sort="Overill, Richard E" uniqKey="Overill R" first="Richard E." last="Overill">Richard E. Overill</name></region></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Musique/explor/WilliamByrdV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000386 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 000386 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Musique
|area= WilliamByrdV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:460CFF3C36C956DD999D7F3A6F79B7908496BE3C
|texte= On the combinatorial complexity of fuzzy pattern matching in music analysis
}}
| This area was generated with Dilib version V0.6.38. |  |